package innersort.radix;

import innersort.speed.SortStrategy;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-03 21:59
 * @ Description :
 */
public class RadixSort implements SortStrategy
{
    public static void main(String[] args)
    {
        int[] array = {53, 3, 542, 748, 14, 214};
        radixSort(array);

    }

    @Override
    public void sort(int[] array)
    {
        radixSort(array);
    }

    private static void radixSort(int[] array)
    {
        //1. 得到序列中最大数的位数
        int max = array[0];
        for (int i = 1; i < array.length; i++)
        {
            if (array[i] > max)
            {
                max = array[i];
            }
        }
        int maxLength = (max + "").length();


        //定义10个桶
        int[][] bucket = new int[10][array.length];
        //定义每个桶中存放的数据个数
        int[] bucketElementCounts = new int[10];


        for (int i = 0, n = 1; i < maxLength; i++, n *= 10)
        {
            //对每个数字的对应位进行排序
            for (int digit : array)
            {
                //取出个位、十位......
                int digitOfElement = digit / n % 10;

                //放入对应桶中,相同位值的数依次排在第二维
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = digit;
                bucketElementCounts[digitOfElement]++;
            }

            //遍历每个桶
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++)
            {
                if (bucketElementCounts[k] != 0)
                {
                    //遍历下标为k的桶
                    for (int l = 0; l < bucketElementCounts[k]; l++)
                    {
                        array[index++] = bucket[k][l];
                    }
                }
                //每轮结束后,将下标为k 的桶中数据总数清空
                bucketElementCounts[k] = 0;
            }
            //System.out.println("第" + (i + 1) + "轮桶排序后的序列为: " + Arrays.toString(array));
        }

    }
}
